# performance_test.py
import time
import random
from collections import deque
from drone import MinCostFlowSolver

def generate_test_case(n, edge_density=0.5):
    """生成测试用例"""
    edges = []
    max_edges = n * (n - 1) // 2
    num_edges = int(max_edges * edge_density)

    # 确保图是连通的
    for i in range(1, n):
        w = random.randint(1, 100)
        edges.append((i, i + 1, w))

    # 添加随机边
    existing_edges = set((min(u, v), max(u, v)) for u, v, w in edges)
    while len(edges) < num_edges:
        u = random.randint(1, n)
        v = random.randint(1, n)
        if u != v and (min(u, v), max(u, v)) not in existing_edges:
            w = random.randint(1, 100)
            edges.append((u, v, w))
            existing_edges.add((min(u, v), max(u, v)))

    return n, len(edges), edges

def run_performance_test():
    """运行性能测试"""
    print("节点数 | 边数 | 执行时间(秒) | 路径总成本 | 是否找到路径")
    print("--------------------------------------------------")

    test_cases = [
        (10, 0.3),  # 小规模稀疏图
        (20, 0.5),  # 中等规模
        (50, 0.3),  # 较大规模稀疏图
        (30, 0.8),  # 中等规模稠密图
        (100, 0.2), # 大规模稀疏图
        (200, 0.1)  # 超大规模稀疏图
    ]

    for n, density in test_cases:
        # 生成测试用例
        n, m, edges = generate_test_case(n, density)

        # 运行并计时
        start_time = time.time()
        solver = MinCostFlowSolver(n, edges)
        path1, path2, total_cost = solver.solve()
        elapsed = time.time() - start_time

        # 检查是否找到路径
        found_path = "是" if path1 and path2 else "否"

        # 打印结果
        print(f"{n:5d} | {m:4d} | {elapsed:.6f} | {total_cost:10} | {found_path}")

if __name__ == "__main__":
    run_performance_test()